package 回文链表;
//请判断一个链表是否为回文链表。
public class Solution
{
    public boolean isPalindrome(ListNode head)
    {
        //遍历到尾结点，与首节点对比，直到两个指针相遇，单向链表，不能从后往前找

        //快慢指针，快指针到尾结点时，慢指针正好到中点，反转后半段的链表，
        //依次对比从中点到首节点的值，不一样则false，最后一样才是true
        //复习一下反转链表
        //判断输入
        if (head==null)
            return true;
        if (head.next==null)
            return true;

        ListNode fast=head;
        ListNode slow=head;

        while (fast!=null&&fast.next!=null)
        {
            slow=slow.next;
            fast=fast.next.next;
        }

        ListNode midNode=Reverse(slow);
       while (head!=null&&midNode!=null)
       {
           if (head.val!=midNode.val)
               return false;
           else
           {
               head=head.next;
               midNode=midNode.next;
           }
       }
       return true;

    }
    //反转链表
    public ListNode Reverse(ListNode head)
    {
        ListNode reversedNode=null;
        ListNode pPrev=null;
        ListNode pNode=head;
        while (pNode!=null)
        {
            ListNode pNext=pNode.next;
            if (pNext==null)
                reversedNode=pNode;
            pNode.next=pPrev;
            pPrev=pNode;
            pNode=pNext;
        }
        return reversedNode;

    }
}
